﻿using System.Collections.Generic;

namespace SKBFirst
{
    class TreeNode : ITreeNode
    {
        private TreeNode lTreeNode;
        private TreeNode rTreeNode;
        private int rank;
        private int balance;

        private int key;
        private int value;
        private IPaginationSet accum;

        private TreeNode()
        {
            
        }

        public static TreeNode Create(IPaginationSet accum)
        {
            return new TreeNode { accum = accum };
        }

        public void Add(int i)
        {
            var treeNodeRoot = rTreeNode;
            if (treeNodeRoot == null)
                rTreeNode = new TreeNode { rank = 1, balance = 0, key = i, value = 0 };
            else
                Move(i);
        }

        public void Slice(int leftIndex, int rightIndex)
        {
            var treePointer = rTreeNode;
            var indexValue = leftIndex;
            var stack = new Stack<TreeNode>();
            while (true)
                if (indexValue < treePointer.rank)
                {
                    stack.Push(treePointer);
                    treePointer = treePointer.lTreeNode;
                }
                else if (indexValue > treePointer.rank + treePointer.value)
                {
                    indexValue = indexValue - (treePointer.rank + treePointer.value);
                    treePointer = treePointer.rTreeNode;
                }
                else
                {
                    var elemCount = rightIndex - leftIndex + 1;
                    
                    for (var i = indexValue - treePointer.rank; i < treePointer.value + 1; i++)
                    {
                        if (elemCount == 0)
                        {
                            accum.NextSet();
                            return;
                        }
                        accum.Put(treePointer.key);
                        elemCount--;
                    }
                    elemCount = LeftToRight(treePointer.rTreeNode, elemCount, accum);
                    while (stack.Count != 0 && elemCount != 0)
                    {
                        treePointer = stack.Pop();
                        for (var i = 0; i < treePointer.value + 1; i++)
                        {
                            if (elemCount == 0)
                            {
                                accum.NextSet();
                                return;
                            }
                            accum.Put(treePointer.key);
                            elemCount--;
                        }
                        elemCount = LeftToRight(treePointer.rTreeNode, elemCount, accum);
                    }
                    accum.NextSet();
                    break;
                }
        }

        private static int LeftToRight(TreeNode treeNodePointer, int elemCount, IPaginationSet outputProcess)
        {
            if (treeNodePointer == null)
                return elemCount;
            elemCount = LeftToRight(treeNodePointer.lTreeNode, elemCount, outputProcess);
            for (int i = 0; i < treeNodePointer.value + 1; i++)
            {
                if (elemCount == 0)
                    return 0;
                outputProcess.Put(treeNodePointer.key);
                elemCount--;
            }
            elemCount = LeftToRight(treeNodePointer.rTreeNode, elemCount, outputProcess);
            return elemCount;
        }

        private void Move(int elemValue)
        {
            TreeNode treeNodePointer = rTreeNode, unbalancedNode = rTreeNode, preUnbalancedNode = this;
            while (true)
            {
                if (elemValue < treeNodePointer.key)
                {
                    var nextNode = treeNodePointer.lTreeNode;
                    treeNodePointer.rank++;
                    if (nextNode == null)
                    {
                        nextNode = new TreeNode { key = elemValue, value = 0, balance = 0, rank = 1};
                        treeNodePointer.lTreeNode = nextNode;
                        InsertAndBalance(unbalancedNode, preUnbalancedNode, elemValue);
                        break;
                    }
                    if (nextNode.balance != 0)
                    {
                        preUnbalancedNode = treeNodePointer;
                        unbalancedNode = nextNode;
                    }
                    treeNodePointer = nextNode;
                }
                else if (elemValue > treeNodePointer.key)
                {
                    var nextNode = treeNodePointer.rTreeNode;
                    if (nextNode == null)
                    {
                        nextNode = new TreeNode { key = elemValue, value = 0, balance = 0, rank = 1 };
                        treeNodePointer.rTreeNode = nextNode;
                        InsertAndBalance(unbalancedNode, preUnbalancedNode, elemValue);
                        break;
                    }
                    if (nextNode.balance != 0)
                    {
                        preUnbalancedNode = treeNodePointer;
                        unbalancedNode = nextNode;
                    }
                    treeNodePointer = nextNode;
                }
                else
                {
                    treeNodePointer.value++;
                    break;
                }
            }
        }

        private static TreeNode Link(int a, TreeNode treeNodePointer)
        {
            return a == -1 ? treeNodePointer.lTreeNode : treeNodePointer.rTreeNode;
        }

        private static void AssignLink(int a, TreeNode treeNodePointer, TreeNode branch)
        {
            if (a == -1)
                treeNodePointer.lTreeNode = branch;
            else
                treeNodePointer.rTreeNode = branch;
        }

        private static TreeNode OneRotate(TreeNode unbalancedBranch, TreeNode unbalancedNode, int balance)
        {
            var treePointer = unbalancedBranch;
            AssignLink(balance, unbalancedNode, Link(-balance, unbalancedBranch));
            AssignLink(-balance, unbalancedBranch, unbalancedNode);
            unbalancedNode.balance = unbalancedBranch.balance = 0;
            if (balance == 1)
                unbalancedBranch.rank = unbalancedBranch.rank + (unbalancedNode.rank + unbalancedNode.value);
            if (balance == -1)
                unbalancedNode.rank = unbalancedNode.rank - (unbalancedBranch.rank + unbalancedNode.value);
            return treePointer;
        }

        private static TreeNode TwoRotate(TreeNode unbalancedBranch, TreeNode unbalancedNode, int balance)
        {
            var treePointer = Link(-balance, unbalancedBranch);
            AssignLink(-balance, unbalancedBranch, Link(balance, treePointer));
            AssignLink(balance, treePointer, unbalancedBranch);
            AssignLink(balance, unbalancedNode, Link(-balance, treePointer));
            AssignLink(-balance, treePointer, unbalancedNode);

            if (treePointer.balance == balance)
            {
                unbalancedNode.balance = -balance;
                unbalancedBranch.balance = 0;
            }
            if (treePointer.balance == 0)
                unbalancedNode.balance = unbalancedBranch.balance = 0;

            if (treePointer.balance == -balance)
            {
                unbalancedNode.balance = 0;
                unbalancedBranch.balance = balance;
            }

            treePointer.balance = 0;

            if (balance == 1)
            {
                unbalancedBranch.rank = unbalancedBranch.rank - (treePointer.rank + treePointer.value);
                treePointer.rank = treePointer.rank + (unbalancedNode.rank + unbalancedNode.value);
            }
            if (balance == -1)
            {
                treePointer.rank = treePointer.rank + (unbalancedBranch.rank + unbalancedBranch.value);
                unbalancedNode.rank = unbalancedNode.rank - (treePointer.rank + treePointer.value);
            }
            return treePointer;
        }

        private static void InsertAndBalance(TreeNode unbalancedNode, TreeNode preUnbalancedNode, int elemValue)
        {
            var balance = elemValue < unbalancedNode.key ? -1 : 1;
            var unbalancedBranch = Link(balance, unbalancedNode);
            var treePointer = unbalancedBranch;

            while (elemValue != treePointer.key)
                if (elemValue < treePointer.key)
                {
                    treePointer.balance = -1;
                    treePointer = treePointer.lTreeNode;
                }
                else if (elemValue > treePointer.key)
                {
                    treePointer.balance = 1;
                    treePointer = treePointer.rTreeNode;
                }

            if (unbalancedNode.balance == 0)
            {
                unbalancedNode.balance = balance;
            } 
            else if (unbalancedNode.balance == -balance)
            {
                unbalancedNode.balance = 0;
            } 
            else if (unbalancedNode.balance == balance)
            {
                if (unbalancedBranch.balance == balance)
                {
                    treePointer = OneRotate(unbalancedBranch, unbalancedNode, balance);
                }
                else if (unbalancedBranch.balance == -balance)
                {
                    treePointer = TwoRotate(unbalancedBranch, unbalancedNode, balance);
                }
                if (unbalancedNode.key == preUnbalancedNode.rTreeNode.key)
                    preUnbalancedNode.rTreeNode = treePointer;
                else
                    preUnbalancedNode.lTreeNode = treePointer;
            }
        }
    }
}
